package arithmetic.someAlgorithm;
/**
 * 两个有序数组合并成一个有序数组的算法实现类
 * @author lidd
 *
 */
public class ArrayMerge {

	/**
	 * 数组合并方法
	 * @param one
	 * @param two
	 * @return
	 */
	public static int[] mergeArray(int one[],int two[]){
        int newArray[];
        //定义一个新数组，长度为两个有序数组长度之和
        newArray = new int[one.length + two.length];
        //i:one数组下标    j：two数组下标  k：newArray新数组下标
        int i=0,j=0,k=0;
        //循环比较两个数组，较小元素的放入新数组，较小元素所在数组下标加一，较大元素对应的数组下标不加一，直到某一个下标等于数组长度时退出循环
        while(i<one.length && j<two.length) {
        	if(one[i] <= two[j]) {
            	newArray[k++] = one[i++];
            }else{
            	newArray[k++] = two[j++];
            }
        }
            
        /* 后面两个while循环是用来保证两个数组比较完之后剩下的一个数组里的元素能顺利都放入新数组
         * 此时较短数组已经全部放入新数组，较长数组还有部分剩余，最后将剩下的部分元素放入新数组，因为数组是有序，所以直接把剩下的顺序加入即可*/
        while(i < one.length) {
        	newArray[k++] = one[i++];
        }
        while(j < two.length) {
        	newArray[k++] = two[j++];
        }
        return newArray;
    }
	
	/**
	 * 数组打印方法
	 * @param arr
	 */
	public static void print(int[] arr) {
		for(int i=0; i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
	}
	
	public static void main(String[] args) {
		int[] one = {1,3,5,7,8,9,14,16,21};
		int[] two = {20,40,60,80,100,110,200,340,450};
		print(mergeArray(one,two));
	}
}
